#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#define swap(type,a,b) {type x=a;a=b;b=x;}

int Getmid(int* a, int left, int right)
{
	int mid = (left + right) >> 1;
	int max = left;
	int min = left;
	if (a[mid] > max)
	{
		max = mid;
	}
	if (a[right] > max)
	{
		max = right;
	}
	if (a[mid] < min)
	{
		min = mid;
	}
	if (a[right] < min)
	{
		min = right;
	}
	return left + right + mid - max - min;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int begin = left, end = right;
	int index = Getmid(a, left, right);
	swap(int, a[begin], a[index]);

	int keyi = begin;
	while (begin < end)
	{
		while (begin < end && a[end] >= a[keyi])
		{
			end--;
		}
		while (begin < end && a[begin] <= a[keyi])
		{
			begin++;
		}
		swap(int, a[begin], a[end]);
	}
	swap(int, a[keyi], a[end]);
	QuickSort(a, left, end - 1);
	QuickSort(a, end + 1, right);
}
int main()
{
	int a[] = { 8,7,5,4,9,10,11 };
	int size = sizeof(a) / sizeof(int);
	QuickSort(a, 0, size - 1);
	int i;
	for (i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}